The present invention relates to analyzing multi-thread programs. More specifically, the invention relates to modifying the predisposed execution of a multi-threaded program to detect and cause latent unsafe accesses to a resource, such as a memory location.
Traditional computer programs involved a single execution stream that performed operations sequentially. However, it is now common for computer programs to include multiple execution streams, which can perform operations in parallel. Each instruction stream is known as a “thread”.
Multi-threaded programs allow for better utilization of the computer system's resources. For example, where a traditional single-threaded program awaits for user input and wastes processing power, a multi-thread program can have a thread perform operations in the “background” while a different thread is processing the user input. Thus, a multi-threaded word processing program can perform spell checking or a multi-threaded spreadsheet program can recalculate the spreadsheet in the background to achieve more efficient utilization of processing power.
Although multi-threaded programs can provide better utilization of the computer system's resources, the dynamic execution of threads makes debugging the programs very difficult. Errors in thread synchronization may be rarely manifested during program execution. This can make the synchronization errors hard to detect, hard to reproduce and hard to verify that an error has been corrected.
In order to detect synchronization errors, it is desirable to determine which resources do not have their access synchronized with synchronization objects, such as a lock. FIG. 1 shows a resource, here a memory location “v,” that is synchronized by a lock “mu.” Before thread 1 writes a value to memory location v, the thread acquires lock mu at an instruction 1. If lock mu is unavailable, the thread will wait, usually suspended, until the lock becomes available.
After thread 1 acquires lock mu, thread 1 writes a value to memory location (i.e., increments v) at an instruction 3. Thread 1 then releases lock mu at an instruction 5 because thread 1 has finished accessing the memory location.
Thread 2 subsequently desires to write data to memory location v. In a manner similar to thread 1, thread 2 acquires lock mu at an instruction 7. Once the lock is acquired, thread 2 writes data to memory location v at an instruction 9 and releases the lock at an instruction 11.
FIG. 1 is a simple illustrating of how accesses to a resource, such as a memory location, may be synchronized using synchronization objects. With this simple example in mind that utilizes a single lock, it may seem easy to determine which accesses to resources have the potential to generate synchronization errors. However, multi-threaded programs are all too often not so simple.
Multi-threaded programs can be constantly acquiring, holding and releasing any number of synchronization objects. Therefore, it can be difficult to determine if access to a resource is or is not managed using synchronization objects. In “Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs,” by Stefan Savage, which is hereby incorporated by reference, techniques for detecting potential synchronization errors or data races are described.
A candidate set C(v) of locks is maintained for each memory location of interest. The candidate set is the intersection of the sets of locks that each thread that accessed a memory location held at the time of access. When a candidate set becomes empty, a potential synchronization error has been detected because no synchronization object controls access to the memory location.
As an example, FIG. 2 shows a method of detecting a potential synchronization error through lock set refinement. There are three columns where the first designated “Program” includes instructions of a computer program, the second designated “locks_held” includes the locks currently held by the execution stream, and the third designated “C(v)” includes the locks that make up the candidate set. Before the first instruction shown in executed, the locks_held is the empty set and the candidate set includes all the possible locks, which is “mu1” and “mu2.” Thus, the execution stream holds no locks and there are two locks that can utilized to synchronize access to the memory location of interest “v.”
At an instruction 101, the execution stream acquires lock mu1. Once the lock is acquired as indicated by the locks_held including the lock mu1, the execution stream writes data to the memory location v at an instruction 103. Since lock mu1 was held when the memory location v was accessed, the candidate set C(v) is set equal to the intersection of the locks_held and the current candidate set. In other words, the intersection of locks_held {mu1} and candidate set {mu1, mu2} is calculated, which {mu1}, so the candidate set becomes {mu1} as indicated in FIG. 2. Lock mu1 is released at an instruction 105 and the locks_held becomes the empty set.
The extension stream acquires lock mu2 at an instruction 107, which makes the locks_held include mu2. At an instruction 109, the memory location v is written to so the candidate set is set equal to the intersection of the locks_held and the candidate set. The intersection of locks_held {mu2} and calculate set {mu1} is the empty set. Thus, the candidate set becomes the empty set as shown. Lock mu2 is released at an instruction 111 and the locks_held becomes the empty set. It should be understood that although the instructions 101-111 were described as being in the same execution stream for simplicity, a multi-threaded program may have performed instructions 101-105 in a first thread and instructions 107-111 in a second thread.
Once the candidate set becomes the empty set, there is a potential synchronization error since there is no lock that restricts access to the memory location of interest. Although the identification of potential synchronization errors is beneficial, there is a need for methods and systems of manipulating multi-threaded programs so that latent synchronization errors will manifest themselves.